#!/usr/bin/python
from __future__ import division
import sys
#collaborators: Sana Imam, Ryan Allan 

intersectionFound = False

#introduce new structures to appease Jack 
class Point: 
	x = 0
	y = 0

	def __init__(self, x, y):
		self.x = x
		self.y = y

	def lessThan(self, otherPoint):
		if self.x<otherPoint.x:
			return True
		elif self.x>otherPoint.x:
			return False
		elif self.y<otherPoint.y:
			return True 
		else:
			return False

class Vector: 
	xCompon = 0
	yCompon = 0 

	#vector from A to B
	def __init__(self, pointA, pointB):
		self.xCompon = pointB.x - pointA.x 
		self.yCompon = pointB.y - pointA.y 


class Flag: 
	x = 0
	y = 0
	slope = 0
	color = "Blank"
	flagType = "none"
	owner = None

	def __init__(self, x, y, slope, color, flagType, owner):
		self.x = x
		self.y = y
		self.slope = slope
		self.color = color 
		self.flagType = flagType
		self.owner = owner

def switchFlags(flagA, flagB): 
	#1 means switch, -1 means don't
	if flagA.x < flagB.x:
		return -1
	elif flagA.x > flagB.x:
		return 1 
	elif flagA.y < flagB.y:
		return -1 
	elif flagA.y > flagB.y: 
		return 1 
	elif flagA.flagType == "terminal" and flagB.flagType == "start":
		return -1 
	elif flagA.flagType == "start" and flagB.flagType == "terminal":
		return 1 
	elif flagA.slope > flagB.slope: 
		return -1
	elif flagA.slope < flagB.slope: 
		return 1
	elif flagA.color == "Blue" and flagB.color == "Red":
		return -1 
	elif flagA.color == "Red" and flagB.color == "Blue":
		return 1
	else: 
		return 0
		#return "dude, stop messin' around. Overlapping lines of same color."

#STILL NEED TO ADD COMPARISON FOR IF POINT LEFT, RIGHT, OR ON LINE. Don't know why. 
class Segment:
	firstPoint = Point(0, 0)
	secondPoint = Point(0, 0)
	color = "Blank"
	startFlag = Flag(0,0,0,"Blank","None",None)
	terminalFlag = Flag(0,0,0,"Blank","None",None)
	flagsSwapped = False
	segmentNumber = 0 

	def __init__(self, pointA, pointB, inputColor, segmentNumber):
		self.firstPoint = pointA
		self.secondPoint = pointB
		self.color = inputColor
		self.segmentNumber = segmentNumber
		self.createFlags(self.firstPoint,self.secondPoint,self.color)

	def createFlags(self,firstPoint,secondPoint,inputColor):
		#calculate slope
		if (firstPoint.x - secondPoint.x) == 0:
			slope = float("inf")
		else: 
			slope = (firstPoint.y - secondPoint.y) / (firstPoint.x - secondPoint.x)
		if(firstPoint.lessThan(secondPoint)): #then firstPoint is startFlag
			self.startFlag = Flag(firstPoint.x,firstPoint.y, slope, self.color, "Start" ,self) 
			self.terminalFlag = Flag(secondPoint.x, secondPoint.y, slope, self.color, "Terminal" , self)
		else:
			self.terminalFlag = Flag(firstPoint.x,firstPoint.y,slope,self.color, "Terminal" ,self) 
			self.startFlag = Flag(secondPoint.x, secondPoint.y, slope, self.color, "Start", self)
			flagsSwapped = True

	def relationToPoint(self,point):
		#use cross product to determine relation
		crazyCrossProd = ((secondPoint.x - firstPoint.x) * (point.y - firstPoint.y) - (secondPoint.y - firstPoint.y) * (point.x - firstPoint.x))
		if crazyCrossProd>0:
			return "Left"
		elif crazyCrossProd<0:
			return "Right"
		else:
			return "On Line"

def outerProduct(vectorA, vectorB):
	return (vectorA.xCompon * vectorB.yCompon) - (vectorA.yCompon * vectorB.xCompon)

def determineIfIntersects(segmentA, segmentB):
	#see CLRS 33 for more info. 
	P_R = Vector(segmentA.firstPoint, segmentB.firstPoint)
	P_S = Vector(segmentA.firstPoint, segmentB.secondPoint)
	P_Q = Vector(segmentA.firstPoint, segmentA.secondPoint)
	Q_R = Vector(segmentA.secondPoint, segmentB.firstPoint)
	S_R = Vector(segmentB.secondPoint, segmentB.firstPoint)

	PR_times_PQ = outerProduct(P_R,P_Q)
	PS_times_PQ = outerProduct(P_S,P_Q)
	PR_times_SR = outerProduct(P_R,S_R)
	QR_times_SR = outerProduct(Q_R,S_R)

	return (PR_times_PQ * PS_times_PQ <0 and PR_times_SR * QR_times_SR <0)


class listDataStructure:

	segments = []

	def __init__(self):
		#create top and bottom sentinel 
		topSentinel = Segment(Point(float("-inf"),float("inf")),Point(float("inf"),float("inf")),"Not relevant",0)
		bottomSentinel = Segment(Point(float("-inf"),float("-inf")),Point(float("inf"),float("-inf")),"Not relevant",0)
		self.segments.append(topSentinel)
		self.segments.append(bottomSentinel)

	def insert(self,passedSegment):
		for segment in self.segments:
			if determineIfIntersects(segment,passedSegment):
				intersectionFound = True
		self.segments.append(passedSegment)

	def remove(self,passedSegment):
		self.segments.remove(passedSegment)


numberOfRuns = sys.argv[2] 

with open(sys.argv[1], 'r') as testFile:
  firstLine = testFile.readline()
  numberOfRed = int(firstLine.split()[0])
  numberOfBlue = int(firstLine.split()[1])
  numberOfProposedCrosses = int(firstLine.split()[2])

  blueLines = []

  for incrementer in range(0,numberOfRed):
  	nextLine = testFile.readline()

  for incrementer in range(0,numberOfBlue):
  	nextLine = testFile.readline()
  	blueLines.append([nextLine.split()[0],nextLine.split()[1],nextLine.split()[2],nextLine.split()[3]])

segmentNumber = 1
allSegments = [] 

for blueLine in blueLines:

	blueA = Point(int(blueLine[0]),int(blueLine[1]))
	blueB = Point(int(blueLine[2]),int(blueLine[3]))
	blueSegment = Segment(blueA, blueB, "Blue", segmentNumber)
	allSegments.append(blueSegment)
	segmentNumber = segmentNumber + 1


sortedFlags = sorted([segment.startFlag for segment in allSegments] + [segment.terminalFlag for segment in allSegments], cmp=switchFlags)


#for flag in sortedFlags:
#	print "{0} {1} {2}".format(flag.owner.segmentNumber,flag.color,flag.flagType)

#now we start SI4. 

#iterate through the x and y positions 
#of the flags to determine mins and maxs 
#so that we can make sentinels??

listDataStructure = listDataStructure()

for i in range(0,int(numberOfRuns)):
	intersectionFound = False
	for flag in sortedFlags:
		if flag.flagType=="Start":
			listDataStructure.insert(flag.owner)
		else: 
			listDataStructure.remove(flag.owner)
	if intersectionFound == False:
		print "VERIFIED"